#include <vector>
#include <unordered_map>

using namespace std;

// 移除最多的同行或同列石头
// n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头
// 如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头
// 给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置
// 返回 可以移除的石子 的最大数量。
// 测试链接 : https://leetcode.cn/problems/most-stones-removed-with-same-row-or-column/

class Solution 
{
private:
    static const int MAXN = 1001;
    int father[MAXN];
    int sets;
    // key : 某行，value : 第一次遇到的石头编号
    unordered_map<int, int> rowFirst;
    // key : 某列，value : 第一次遇到的石头编号
    unordered_map<int, int> colFirst;

    void Build(int n)
    {
        sets = n;
        rowFirst.clear();
        colFirst.clear();
        for(int i = 0; i < n; ++i) father[i] = i;
    }

    int Find(int i)
    {
        return i == father[i] ? i : father[i] = Find(father[i]);
    }

    void Union(int x, int y)
    {
        int fx = Find(x);
        int fy = Find(y);
        if(fx != fy)
        {
            --sets;
            father[fx] = fy;
        }
    }

public:
    int removeStones(vector<vector<int>>& stones) 
    {
        int n = stones.size();
        Build(n);
        for(int i = 0; i < n; ++i)
        {
            int row = stones[i][0], col = stones[i][1];
            if(!rowFirst.count(row)) rowFirst[row] = i;
            else Union(rowFirst[row], i);
            
            if(!colFirst.count(col)) colFirst[col] = i;
            else Union(colFirst[col], i);
        }
        return n - sets;
    }
};